/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 24
 * Time: 21:47
 */
//牛客 链表的奇偶重排
public class Solution3 {
    //法一 我的方法
    public static ListNode oddEvenList (ListNode head) {
        if(head == null) return null;
        ListNode dummyNode1 = new ListNode(-1);
        ListNode cur1 = dummyNode1;
        ListNode dummyNode2 = new ListNode(-1);
        ListNode cur2 = dummyNode2;
        ListNode cur = head;
        while(cur != null) {
            cur1.next = cur;
            cur1 = cur1.next;
            cur = cur.next;
            if(cur != null) {//这一步要写
                cur2.next = cur;
                cur2 = cur2.next;
                cur = cur.next;
            }
        }
        cur1.next = dummyNode2.next;
        if(cur2.next != null) cur2.next = null;//这一步要写
        return dummyNode1.next;
    }

    //法二 官方方法
    public static ListNode oddEvenList1 (ListNode head) {
        if(head == null) return null;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while(even != null && even.next != null) {//这个条件很重要，因为下面相当于有even.next.next
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}
